package com.copa.l78;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author copa
 * @createDate 2022-05-17 17:07
 * @function DFS 一开始就想到了回溯法...但没想到是无意间用了DFS（深度优先遍历）了
 */
public class Test1 {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 防止给出的数组是乱序的
        Arrays.sort(nums);
        backTracking(nums, result, 0, new ArrayList<>());
        return result;
    }

    private void backTracking(int[] nums,
                              List<List<Integer>> result,
                              int startIndex,
                              ArrayList<Integer> tempList) {
        // 这里就添加到结果集了
        result.add(new ArrayList<>(tempList));
        // 这个终止条件可用可不用，因为DFS就是不撞南墙不回头 要写的话如下
//        if (nums.length == startIndex) {
//            return;
//        }
        for (int i = startIndex; i < nums.length; i++) {
            tempList.add(nums[i]);
            // 这个也是用了剪枝的方式，直接判断下一个遍历的元素，无需重复判断
            backTracking(nums, result,i + 1, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        List<List<Integer>> result = new Test1().subsets(nums);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
